<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">


<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>pgmpy.estimators.ConstraintBasedEstimator &#8212; pgmpy 0.1.2 documentation</title>
    
    <link rel="stylesheet" href="../../../_static/sphinxdoc.css" type="text/css" />
    <link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '../../../',
        VERSION:     '0.1.2',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true,
        SOURCELINK_SUFFIX: '.txt'
      };
    </script>
    <script type="text/javascript" src="../../../_static/jquery.js"></script>
    <script type="text/javascript" src="../../../_static/underscore.js"></script>
    <script type="text/javascript" src="../../../_static/doctools.js"></script>
    <link rel="index" title="Index" href="../../../genindex.html" />
    <link rel="search" title="Search" href="../../../search.html" /> 
  </head>
  <body role="document">
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">pgmpy 0.1.2 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" accesskey="U">Module code</a> &#187;</li> 
      </ul>
    </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../../../index.html">
              <img class="logo" src="../../../_static/logo.png" alt="Logo"/>
            </a></p>
<div id="searchbox" style="display: none" role="search">
  <h3>Quick search</h3>
    <form class="search" action="../../../search.html" method="get">
      <div><input type="text" name="q" /></div>
      <div><input type="submit" value="Go" /></div>
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <h1>Source code for pgmpy.estimators.ConstraintBasedEstimator</h1><div class="highlight"><pre>
<span></span><span class="ch">#!/usr/bin/env python</span>

<span class="kn">from</span> <span class="nn">warnings</span> <span class="k">import</span> <span class="n">warn</span>
<span class="kn">from</span> <span class="nn">itertools</span> <span class="k">import</span> <span class="n">combinations</span>

<span class="kn">from</span> <span class="nn">pgmpy.base</span> <span class="k">import</span> <span class="n">UndirectedGraph</span>
<span class="kn">from</span> <span class="nn">pgmpy.models</span> <span class="k">import</span> <span class="n">BayesianModel</span>
<span class="kn">from</span> <span class="nn">pgmpy.estimators</span> <span class="k">import</span> <span class="n">StructureEstimator</span>
<span class="kn">from</span> <span class="nn">pgmpy.independencies</span> <span class="k">import</span> <span class="n">Independencies</span><span class="p">,</span> <span class="n">IndependenceAssertion</span>


<div class="viewcode-block" id="ConstraintBasedEstimator"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator">[docs]</a><span class="k">class</span> <span class="nc">ConstraintBasedEstimator</span><span class="p">(</span><span class="n">StructureEstimator</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">data</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Class for constraint-based estimation of BayesianModels from a given</span>
<span class="sd">        data set. Identifies (conditional) dependencies in data set using</span>
<span class="sd">        chi_square dependency test and uses the PC algorithm to estimate a DAG</span>
<span class="sd">        pattern that satisfies the identified dependencies. The DAG pattern can</span>
<span class="sd">        then be completed to a faithful BayesianModel, if possible.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        data: pandas DataFrame object</span>
<span class="sd">            datafame object where each column represents one variable.</span>
<span class="sd">            (If some values in the data are missing the data cells should be set to `numpy.NaN`.</span>
<span class="sd">            Note that pandas converts each column containing `numpy.NaN`s to dtype `float`.)</span>

<span class="sd">        state_names: dict (optional)</span>
<span class="sd">            A dict indicating, for each variable, the discrete set of states (or values)</span>
<span class="sd">            that the variable can take. If unspecified, the observed values in the data set</span>
<span class="sd">            are taken to be the only possible states.</span>

<span class="sd">        complete_samples_only: bool (optional, default `True`)</span>
<span class="sd">            Specifies how to deal with missing data, if present. If set to `True` all rows</span>
<span class="sd">            that contain `np.Nan` somewhere are ignored. If `False` then, for each variable,</span>
<span class="sd">            every row where neither the variable nor its parents are `np.NaN` is used.</span>
<span class="sd">            This sets the behavior of the `state_count`-method.</span>

<span class="sd">        References</span>
<span class="sd">        ----------</span>
<span class="sd">        [1] Koller &amp; Friedman, Probabilistic Graphical Models - Principles and Techniques,</span>
<span class="sd">            2009, Section 18.2</span>
<span class="sd">        [2] Neapolitan, Learning Bayesian Networks, Section 10.1.2 for the PC algorithm (page 550),</span>
<span class="sd">        http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">ConstraintBasedEstimator</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">)</span>

<div class="viewcode-block" id="ConstraintBasedEstimator.estimate"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.estimate">[docs]</a>    <span class="k">def</span> <span class="nf">estimate</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">significance_level</span><span class="o">=</span><span class="mf">0.01</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Estimates a BayesianModel for the data set, using the PC contraint-based</span>
<span class="sd">        structure learning algorithm. Independencies are identified from the</span>
<span class="sd">        data set using a chi-squared statistic with the acceptance threshold of</span>
<span class="sd">        `significance_level`. PC identifies a partially directed acyclic graph (PDAG), given</span>
<span class="sd">        that the tested independencies admit a faithful Bayesian network representation.</span>
<span class="sd">        This method returns a BayesianModel that is a completion of this PDAG.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        significance_level: float, default: 0.01</span>
<span class="sd">            The significance level to use for conditional independence tests in the data set.</span>

<span class="sd">            `significance_level` is the desired Type 1 error probability of</span>
<span class="sd">            falsely rejecting the null hypothesis that variables are independent,</span>
<span class="sd">            given that they are. The lower `significance_level`, the less likely</span>
<span class="sd">            we are to accept dependencies, resulting in a sparser graph.</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        model: BayesianModel()-instance</span>
<span class="sd">            An estimate for the BayesianModel for the data set (not yet parametrized).</span>

<span class="sd">        Reference</span>
<span class="sd">        ---------</span>
<span class="sd">        Neapolitan, Learning Bayesian Networks, Section 10.1.2, Algorithm 10.2 (page 550)</span>
<span class="sd">        http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; import pandas as pd</span>
<span class="sd">        &gt;&gt;&gt; import numpy as np</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.estimators import ConstraintBasedEstimator</span>
<span class="sd">        &gt;&gt;&gt; data = pd.DataFrame(np.random.randint(0, 5, size=(2500, 3)), columns=list(&#39;XYZ&#39;))</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;sum&#39;] = data.sum(axis=1)</span>
<span class="sd">        &gt;&gt;&gt; print(data)</span>
<span class="sd">              X  Y  Z  sum</span>
<span class="sd">        0     3  0  1    4</span>
<span class="sd">        1     1  4  3    8</span>
<span class="sd">        2     0  0  3    3</span>
<span class="sd">        3     0  2  3    5</span>
<span class="sd">        4     2  1  1    4</span>
<span class="sd">        ...  .. .. ..  ...</span>
<span class="sd">        2495  2  3  0    5</span>
<span class="sd">        2496  1  1  2    4</span>
<span class="sd">        2497  0  4  2    6</span>
<span class="sd">        2498  0  0  0    0</span>
<span class="sd">        2499  2  4  0    6</span>

<span class="sd">        [2500 rows x 4 columns]</span>
<span class="sd">        &gt;&gt;&gt; c = ConstraintBasedEstimator(data)</span>
<span class="sd">        &gt;&gt;&gt; model = c.estimate()</span>
<span class="sd">        &gt;&gt;&gt; print(model.edges())</span>
<span class="sd">        [(&#39;Z&#39;, &#39;sum&#39;), (&#39;X&#39;, &#39;sum&#39;), (&#39;Y&#39;, &#39;sum&#39;)]</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">estimate_skeleton</span><span class="p">(</span><span class="n">significance_level</span><span class="p">)</span>
        <span class="n">pdag</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">skeleton_to_pdag</span><span class="p">(</span><span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span><span class="p">)</span>
        <span class="n">model</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pdag_to_dag</span><span class="p">(</span><span class="n">pdag</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">model</span></div>

<div class="viewcode-block" id="ConstraintBasedEstimator.estimate_skeleton"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.estimate_skeleton">[docs]</a>    <span class="k">def</span> <span class="nf">estimate_skeleton</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">significance_level</span><span class="o">=</span><span class="mf">0.01</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Estimates a graph skeleton (UndirectedGraph) for the data set.</span>
<span class="sd">        Uses the build_skeleton method (PC algorithm); independencies are</span>
<span class="sd">        determined using a chisquare statistic with the acceptance threshold</span>
<span class="sd">        of `significance_level`. Returns a tuple `(skeleton, separating_sets).</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        significance_level: float, default: 0.01</span>
<span class="sd">            The significance level to use for conditional independence tests in the data set.</span>

<span class="sd">            `significance_level` is the desired Type 1 error probability of</span>
<span class="sd">            falsely rejecting the null hypothesis that variables are independent,</span>
<span class="sd">            given that they are. The lower `significance_level`, the less likely</span>
<span class="sd">            we are to accept dependencies, resulting in a sparser graph.</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        skeleton: UndirectedGraph</span>
<span class="sd">            An estimate for the undirected graph skeleton of the BN underlying the data.</span>

<span class="sd">        separating_sets: dict</span>
<span class="sd">            A dict containing for each pair of not directly connected nodes a</span>
<span class="sd">            separating set of variables that makes then conditionally independent.</span>
<span class="sd">            (needed for edge orientation procedures)</span>

<span class="sd">        Reference</span>
<span class="sd">        ---------</span>
<span class="sd">        [1] Neapolitan, Learning Bayesian Networks, Section 10.1.2, Algorithm 10.2 (page 550)</span>
<span class="sd">            http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf</span>
<span class="sd">        [2] Chi-square test https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test#Test_of_independence</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; import pandas as pd</span>
<span class="sd">        &gt;&gt;&gt; import numpy as np</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.estimators import ConstraintBasedEstimator</span>
<span class="sd">        &gt;&gt;&gt;</span>
<span class="sd">        &gt;&gt;&gt; data = pd.DataFrame(np.random.randint(0, 2, size=(5000, 5)), columns=list(&#39;ABCDE&#39;))</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;F&#39;] = data[&#39;A&#39;] + data[&#39;B&#39;] + data [&#39;C&#39;]</span>
<span class="sd">        &gt;&gt;&gt; est = ConstraintBasedEstimator(data)</span>
<span class="sd">        &gt;&gt;&gt; skel, sep_sets = est.estimate_skeleton()</span>
<span class="sd">        &gt;&gt;&gt; skel.edges()</span>
<span class="sd">        [(&#39;A&#39;, &#39;F&#39;), (&#39;B&#39;, &#39;F&#39;), (&#39;C&#39;, &#39;F&#39;)]</span>
<span class="sd">        &gt;&gt;&gt; # all independencies are unconditional:</span>
<span class="sd">        &gt;&gt;&gt; sep_sets</span>
<span class="sd">        {(&#39;D&#39;, &#39;A&#39;): (), (&#39;C&#39;, &#39;A&#39;): (), (&#39;C&#39;, &#39;E&#39;): (), (&#39;E&#39;, &#39;F&#39;): (), (&#39;B&#39;, &#39;D&#39;): (),</span>
<span class="sd">         (&#39;B&#39;, &#39;E&#39;): (), (&#39;D&#39;, &#39;F&#39;): (), (&#39;D&#39;, &#39;E&#39;): (), (&#39;A&#39;, &#39;E&#39;): (), (&#39;B&#39;, &#39;A&#39;): (),</span>
<span class="sd">         (&#39;B&#39;, &#39;C&#39;): (), (&#39;C&#39;, &#39;D&#39;): ()}</span>
<span class="sd">        &gt;&gt;&gt;</span>
<span class="sd">        &gt;&gt;&gt; data = pd.DataFrame(np.random.randint(0, 2, size=(5000, 3)), columns=list(&#39;XYZ&#39;))</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;X&#39;] += data[&#39;Z&#39;]</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;Y&#39;] += data[&#39;Z&#39;]</span>
<span class="sd">        &gt;&gt;&gt; est = ConstraintBasedEstimator(data)</span>
<span class="sd">        &gt;&gt;&gt; skel, sep_sets = est.estimate_skeleton()</span>
<span class="sd">        &gt;&gt;&gt; skel.edges()</span>
<span class="sd">        [(&#39;X&#39;, &#39;Z&#39;), (&#39;Y&#39;, &#39;Z&#39;)]</span>
<span class="sd">        &gt;&gt;&gt; # X, Y dependent, but conditionally independent given Z:</span>
<span class="sd">        &gt;&gt;&gt; sep_sets</span>
<span class="sd">        {(&#39;X&#39;, &#39;Y&#39;): (&#39;Z&#39;,)}</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">nodes</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">state_names</span><span class="o">.</span><span class="n">keys</span><span class="p">()</span>

        <span class="k">def</span> <span class="nf">is_independent</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">,</span> <span class="n">Zs</span><span class="p">):</span>
            <span class="sd">&quot;&quot;&quot;Returns result of hypothesis test for the null hypothesis that</span>
<span class="sd">            X _|_ Y | Zs, using a chi2 statistic and threshold `significance_level`.</span>
<span class="sd">            &quot;&quot;&quot;</span>
            <span class="n">chi2</span><span class="p">,</span> <span class="n">p_value</span><span class="p">,</span> <span class="n">sufficient_data</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">test_conditional_independence</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">,</span> <span class="n">Zs</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">p_value</span> <span class="o">&gt;=</span> <span class="n">significance_level</span>

        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">build_skeleton</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span> <span class="n">is_independent</span><span class="p">)</span></div>

    <span class="nd">@staticmethod</span>
<div class="viewcode-block" id="ConstraintBasedEstimator.estimate_from_independencies"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.estimate_from_independencies">[docs]</a>    <span class="k">def</span> <span class="nf">estimate_from_independencies</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span> <span class="n">independencies</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Estimates a BayesianModel from an Independencies()-object or a</span>
<span class="sd">        decision function for conditional independencies. This requires that</span>
<span class="sd">        the set of independencies admits a faithful representation (e.g. is a</span>
<span class="sd">        set of d-seperation for some BN or is closed under the semi-graphoid</span>
<span class="sd">        axioms). See `build_skeleton`, `skeleton_to_pdag`, `pdag_to_dag` for</span>
<span class="sd">        details.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        nodes: list, array-like</span>
<span class="sd">            A list of node/variable names of the network skeleton.</span>

<span class="sd">        independencies: Independencies-instance or function.</span>
<span class="sd">            The source of independency information from which to build the skeleton.</span>
<span class="sd">            The provided Independencies should admit a faithful representation.</span>
<span class="sd">            Can either be provided as an Independencies()-instance or by passing a</span>
<span class="sd">            function `f(X, Y, Zs)` that returns `True` when X _|_ Y | Zs,</span>
<span class="sd">            otherwise `False`. (X, Y being individual nodes and Zs a list of nodes).</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        model: BayesianModel instance</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.estimators import ConstraintBasedEstimator</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.models import BayesianModel</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.independencies import Independencies</span>

<span class="sd">        &gt;&gt;&gt; ind = Independencies([&#39;B&#39;, &#39;C&#39;], [&#39;A&#39;, [&#39;B&#39;, &#39;C&#39;], &#39;D&#39;])</span>
<span class="sd">        &gt;&gt;&gt; ind = ind.closure()</span>
<span class="sd">        &gt;&gt;&gt; skel = ConstraintBasedEstimator.estimate_from_independencies(&quot;ABCD&quot;, ind)</span>
<span class="sd">        &gt;&gt;&gt; print(skel.edges())</span>
<span class="sd">        [(&#39;B&#39;, &#39;D&#39;), (&#39;A&#39;, &#39;D&#39;), (&#39;C&#39;, &#39;D&#39;)]</span>

<span class="sd">        &gt;&gt;&gt; model = BayesianModel([(&#39;A&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;D&#39;), (&#39;C&#39;, &#39;E&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; skel = ConstraintBasedEstimator.estimate_from_independencies(model.nodes(), model.get_independencies())</span>
<span class="sd">        &gt;&gt;&gt; print(skel.edges())</span>
<span class="sd">        [(&#39;B&#39;, &#39;C&#39;), (&#39;A&#39;, &#39;C&#39;), (&#39;C&#39;, &#39;E&#39;), (&#39;D&#39;, &#39;B&#39;)]</span>
<span class="sd">        &gt;&gt;&gt; # note that (&#39;D&#39;, &#39;B&#39;) is flipped compared to the original network;</span>
<span class="sd">        &gt;&gt;&gt; # Both networks belong to the same PDAG/are I-equivalent</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span> <span class="o">=</span> <span class="n">ConstraintBasedEstimator</span><span class="o">.</span><span class="n">build_skeleton</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span> <span class="n">independencies</span><span class="p">)</span>
        <span class="n">pdag</span> <span class="o">=</span> <span class="n">ConstraintBasedEstimator</span><span class="o">.</span><span class="n">skeleton_to_pdag</span><span class="p">(</span><span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span><span class="p">)</span>
        <span class="n">dag</span> <span class="o">=</span> <span class="n">ConstraintBasedEstimator</span><span class="o">.</span><span class="n">pdag_to_dag</span><span class="p">(</span><span class="n">pdag</span><span class="p">)</span>

        <span class="k">return</span> <span class="n">dag</span></div>

    <span class="nd">@staticmethod</span>
<div class="viewcode-block" id="ConstraintBasedEstimator.pdag_to_dag"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.pdag_to_dag">[docs]</a>    <span class="k">def</span> <span class="nf">pdag_to_dag</span><span class="p">(</span><span class="n">pdag</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Completes a PDAG to a DAG, without adding v-structures, if such a</span>
<span class="sd">        completion exists. If no faithful extension is possible, some fully</span>
<span class="sd">        oriented DAG that corresponds to the PDAG is returned and a warning is</span>
<span class="sd">        generated. This is a static method.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        pdag: DirectedGraph</span>
<span class="sd">            A directed acyclic graph pattern, consisting in (acyclic) directed edges</span>
<span class="sd">            as well as &quot;undirected&quot; edges, represented as both-way edges between</span>
<span class="sd">            nodes.</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        dag: BayesianModel</span>
<span class="sd">            A faithful orientation of pdag, if one exists. Otherwise any</span>
<span class="sd">            fully orientated DAG/BayesianModel with the structure of pdag.</span>

<span class="sd">        References</span>
<span class="sd">        ----------</span>
<span class="sd">        [1] Chickering, Learning Equivalence Classes of Bayesian-Network Structures,</span>
<span class="sd">            2002; See page 454 (last paragraph) for the algorithm pdag_to_dag</span>
<span class="sd">            http://www.jmlr.org/papers/volume2/chickering02a/chickering02a.pdf</span>
<span class="sd">        [2] Dor &amp; Tarsi, A simple algorithm to construct a consistent extension</span>
<span class="sd">            of a partially oriented graph, 1992,</span>
<span class="sd">            http://ftp.cs.ucla.edu/pub/stat_ser/r185-dor-tarsi.pdf</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; import pandas as pd</span>
<span class="sd">        &gt;&gt;&gt; import numpy as np</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.base import DirectedGraph</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.estimators import ConstraintBasedEstimator</span>
<span class="sd">        &gt;&gt;&gt; data = pd.DataFrame(np.random.randint(0, 4, size=(5000, 3)), columns=list(&#39;ABD&#39;))</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;C&#39;] = data[&#39;A&#39;] - data[&#39;B&#39;]</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;D&#39;] += data[&#39;A&#39;]</span>
<span class="sd">        &gt;&gt;&gt; c = ConstraintBasedEstimator(data)</span>
<span class="sd">        &gt;&gt;&gt; pdag = c.skeleton_to_pdag(*c.estimate_skeleton())</span>
<span class="sd">        &gt;&gt;&gt; pdag.edges()</span>
<span class="sd">        [(&#39;B&#39;, &#39;C&#39;), (&#39;D&#39;, &#39;A&#39;), (&#39;A&#39;, &#39;D&#39;), (&#39;A&#39;, &#39;C&#39;)]</span>
<span class="sd">        &gt;&gt;&gt; c.pdag_to_dag(pdag).edges()</span>
<span class="sd">        [(&#39;B&#39;, &#39;C&#39;), (&#39;A&#39;, &#39;D&#39;), (&#39;A&#39;, &#39;C&#39;)]</span>

<span class="sd">        &gt;&gt;&gt; # pdag_to_dag is static:</span>
<span class="sd">        ... pdag1 = DirectedGraph([(&#39;A&#39;, &#39;B&#39;), (&#39;C&#39;, &#39;B&#39;), (&#39;C&#39;, &#39;D&#39;), (&#39;D&#39;, &#39;C&#39;), (&#39;D&#39;, &#39;A&#39;), (&#39;A&#39;, &#39;D&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; ConstraintBasedEstimator.pdag_to_dag(pdag1).edges()</span>
<span class="sd">        [(&#39;D&#39;, &#39;C&#39;), (&#39;C&#39;, &#39;B&#39;), (&#39;A&#39;, &#39;B&#39;), (&#39;A&#39;, &#39;D&#39;)]</span>

<span class="sd">        &gt;&gt;&gt; # example of a pdag with no faithful extension:</span>
<span class="sd">        ... pdag2 = DirectedGraph([(&#39;A&#39;, &#39;B&#39;), (&#39;A&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;C&#39;), (&#39;C&#39;, &#39;B&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; ConstraintBasedEstimator.pdag_to_dag(pdag2).edges()</span>
<span class="sd">        UserWarning: PDAG has no faithful extension (= no oriented DAG with the same v-structures as PDAG).</span>
<span class="sd">        Remaining undirected PDAG edges oriented arbitrarily.</span>
<span class="sd">        [(&#39;B&#39;, &#39;C&#39;), (&#39;A&#39;, &#39;B&#39;), (&#39;A&#39;, &#39;C&#39;)]</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">pdag</span> <span class="o">=</span> <span class="n">pdag</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
        <span class="n">dag</span> <span class="o">=</span> <span class="n">BayesianModel</span><span class="p">()</span>
        <span class="n">dag</span><span class="o">.</span><span class="n">add_nodes_from</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">nodes</span><span class="p">())</span>

        <span class="c1"># add already directed edges of pdag to dag</span>
        <span class="k">for</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">pdag</span><span class="o">.</span><span class="n">edges</span><span class="p">():</span>
            <span class="k">if</span> <span class="ow">not</span> <span class="n">pdag</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">Y</span><span class="p">,</span> <span class="n">X</span><span class="p">):</span>
                <span class="n">dag</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">)</span>

        <span class="k">while</span> <span class="n">pdag</span><span class="o">.</span><span class="n">number_of_nodes</span><span class="p">()</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="c1"># find node with (1) no directed outgoing edges and</span>
            <span class="c1">#                (2) the set of undirected neighbors is either empty or</span>
            <span class="c1">#                    undirected neighbors + parents of X are a clique</span>
            <span class="n">found</span> <span class="o">=</span> <span class="kc">False</span>
            <span class="k">for</span> <span class="n">X</span> <span class="ow">in</span> <span class="n">pdag</span><span class="o">.</span><span class="n">nodes</span><span class="p">():</span>
                <span class="n">directed_outgoing_edges</span> <span class="o">=</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">-</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span>
                <span class="n">undirected_neighbors</span> <span class="o">=</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">&amp;</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span>
                <span class="n">neighbors_are_clique</span> <span class="o">=</span> <span class="nb">all</span><span class="p">((</span><span class="n">pdag</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">Y</span><span class="p">,</span> <span class="n">Z</span><span class="p">)</span>
                                            <span class="k">for</span> <span class="n">Z</span> <span class="ow">in</span> <span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">)</span>
                                            <span class="k">for</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">undirected_neighbors</span> <span class="k">if</span> <span class="ow">not</span> <span class="n">Y</span> <span class="o">==</span> <span class="n">Z</span><span class="p">))</span>

                <span class="k">if</span> <span class="ow">not</span> <span class="n">directed_outgoing_edges</span> <span class="ow">and</span> \
                        <span class="p">(</span><span class="ow">not</span> <span class="n">undirected_neighbors</span> <span class="ow">or</span> <span class="n">neighbors_are_clique</span><span class="p">):</span>
                    <span class="n">found</span> <span class="o">=</span> <span class="kc">True</span>
                    <span class="c1"># add all edges of X as outgoing edges to dag</span>
                    <span class="k">for</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">):</span>
                        <span class="n">dag</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">Y</span><span class="p">,</span> <span class="n">X</span><span class="p">)</span>

                    <span class="n">pdag</span><span class="o">.</span><span class="n">remove_node</span><span class="p">(</span><span class="n">X</span><span class="p">)</span>
                    <span class="k">break</span>

            <span class="k">if</span> <span class="ow">not</span> <span class="n">found</span><span class="p">:</span>
                <span class="n">warn</span><span class="p">(</span><span class="s2">&quot;PDAG has no faithful extension (= no oriented DAG with the &quot;</span> <span class="o">+</span>
                     <span class="s2">&quot;same v-structures as PDAG). Remaining undirected PDAG edges &quot;</span> <span class="o">+</span>
                     <span class="s2">&quot;oriented arbitrarily.&quot;</span><span class="p">)</span>
                <span class="k">for</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">pdag</span><span class="o">.</span><span class="n">edges</span><span class="p">():</span>
                    <span class="k">if</span> <span class="ow">not</span> <span class="n">dag</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">Y</span><span class="p">,</span> <span class="n">X</span><span class="p">):</span>
                        <span class="k">try</span><span class="p">:</span>
                            <span class="n">dag</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">)</span>
                        <span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
                            <span class="k">pass</span>
                <span class="k">break</span>

        <span class="k">return</span> <span class="n">dag</span></div>

    <span class="nd">@staticmethod</span>
<div class="viewcode-block" id="ConstraintBasedEstimator.model_to_pdag"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.model_to_pdag">[docs]</a>    <span class="k">def</span> <span class="nf">model_to_pdag</span><span class="p">(</span><span class="n">model</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Construct the DAG pattern (representing the I-equivalence class) for</span>
<span class="sd">        a given BayesianModel. This is the &quot;inverse&quot; to pdag_to_dag.</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">model</span><span class="p">,</span> <span class="n">BayesianModel</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;model: Expected BayesianModel instance, &quot;</span> <span class="o">+</span>
                            <span class="s2">&quot;got type </span><span class="si">{model_type}</span><span class="s2">&quot;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="n">model_type</span><span class="o">=</span><span class="nb">type</span><span class="p">(</span><span class="n">model</span><span class="p">)))</span>

        <span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span> <span class="o">=</span> <span class="n">ConstraintBasedEstimator</span><span class="o">.</span><span class="n">build_skeleton</span><span class="p">(</span>
                                    <span class="n">model</span><span class="o">.</span><span class="n">nodes</span><span class="p">(),</span>
                                    <span class="n">model</span><span class="o">.</span><span class="n">get_independencies</span><span class="p">())</span>
        <span class="n">pdag</span> <span class="o">=</span> <span class="n">ConstraintBasedEstimator</span><span class="o">.</span><span class="n">skeleton_to_pdag</span><span class="p">(</span><span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span><span class="p">)</span>

        <span class="k">return</span> <span class="n">pdag</span></div>

    <span class="nd">@staticmethod</span>
<div class="viewcode-block" id="ConstraintBasedEstimator.skeleton_to_pdag"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.skeleton_to_pdag">[docs]</a>    <span class="k">def</span> <span class="nf">skeleton_to_pdag</span><span class="p">(</span><span class="n">skel</span><span class="p">,</span> <span class="n">separating_sets</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Orients the edges of a graph skeleton based on information from</span>
<span class="sd">        `separating_sets` to form a DAG pattern (DirectedGraph).</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        skel: UndirectedGraph</span>
<span class="sd">            An undirected graph skeleton as e.g. produced by the</span>
<span class="sd">            estimate_skeleton method.</span>

<span class="sd">        separating_sets: dict</span>
<span class="sd">            A dict containing for each pair of not directly connected nodes a</span>
<span class="sd">            separating set (&quot;witnessing set&quot;) of variables that makes then</span>
<span class="sd">            conditionally independent. (needed for edge orientation)</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        pdag: DirectedGraph</span>
<span class="sd">            An estimate for the DAG pattern of the BN underlying the data. The</span>
<span class="sd">            graph might contain some nodes with both-way edges (X-&gt;Y and Y-&gt;X).</span>
<span class="sd">            Any completion by (removing one of the both-way edges for each such</span>
<span class="sd">            pair) results in a I-equivalent Bayesian network DAG.</span>

<span class="sd">        Reference</span>
<span class="sd">        ---------</span>
<span class="sd">        Neapolitan, Learning Bayesian Networks, Section 10.1.2, Algorithm 10.2 (page 550)</span>
<span class="sd">        http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf</span>


<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; import pandas as pd</span>
<span class="sd">        &gt;&gt;&gt; import numpy as np</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.estimators import ConstraintBasedEstimator</span>
<span class="sd">        &gt;&gt;&gt; data = pd.DataFrame(np.random.randint(0, 4, size=(5000, 3)), columns=list(&#39;ABD&#39;))</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;C&#39;] = data[&#39;A&#39;] - data[&#39;B&#39;]</span>
<span class="sd">        &gt;&gt;&gt; data[&#39;D&#39;] += data[&#39;A&#39;]</span>
<span class="sd">        &gt;&gt;&gt; c = ConstraintBasedEstimator(data)</span>
<span class="sd">        &gt;&gt;&gt; pdag = c.skeleton_to_pdag(*c.estimate_skeleton())</span>
<span class="sd">        &gt;&gt;&gt; pdag.edges() # edges: A-&gt;C, B-&gt;C, A--D (not directed)</span>
<span class="sd">        [(&#39;B&#39;, &#39;C&#39;), (&#39;A&#39;, &#39;C&#39;), (&#39;A&#39;, &#39;D&#39;), (&#39;D&#39;, &#39;A&#39;)]</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">pdag</span> <span class="o">=</span> <span class="n">skel</span><span class="o">.</span><span class="n">to_directed</span><span class="p">()</span>
        <span class="n">node_pairs</span> <span class="o">=</span> <span class="n">combinations</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">nodes</span><span class="p">(),</span> <span class="mi">2</span><span class="p">)</span>

        <span class="c1"># 1) for each X-Z-Y, if Z not in the separating set of X,Y, then orient edges as X-&gt;Z&lt;-Y</span>
        <span class="c1"># (Algorithm 3.4 in Koller &amp; Friedman PGM, page 86)</span>
        <span class="k">for</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">node_pairs</span><span class="p">:</span>
            <span class="k">if</span> <span class="ow">not</span> <span class="n">skel</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">):</span>
                <span class="k">for</span> <span class="n">Z</span> <span class="ow">in</span> <span class="nb">set</span><span class="p">(</span><span class="n">skel</span><span class="o">.</span><span class="n">neighbors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">&amp;</span> <span class="nb">set</span><span class="p">(</span><span class="n">skel</span><span class="o">.</span><span class="n">neighbors</span><span class="p">(</span><span class="n">Y</span><span class="p">)):</span>
                    <span class="k">if</span> <span class="n">Z</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">separating_sets</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">((</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">))]:</span>
                        <span class="n">pdag</span><span class="o">.</span><span class="n">remove_edges_from</span><span class="p">([(</span><span class="n">Z</span><span class="p">,</span> <span class="n">X</span><span class="p">),</span> <span class="p">(</span><span class="n">Z</span><span class="p">,</span> <span class="n">Y</span><span class="p">)])</span>

        <span class="n">progress</span> <span class="o">=</span> <span class="kc">True</span>
        <span class="k">while</span> <span class="n">progress</span><span class="p">:</span>  <span class="c1"># as long as edges can be oriented (removed)</span>
            <span class="n">num_edges</span> <span class="o">=</span> <span class="n">pdag</span><span class="o">.</span><span class="n">number_of_edges</span><span class="p">()</span>

            <span class="c1"># 2) for each X-&gt;Z-Y, orient edges to Z-&gt;Y</span>
            <span class="k">for</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">node_pairs</span><span class="p">:</span>
                <span class="k">for</span> <span class="n">Z</span> <span class="ow">in</span> <span class="p">((</span><span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">-</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">)))</span> <span class="o">&amp;</span>
                          <span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">Y</span><span class="p">))</span> <span class="o">&amp;</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">Y</span><span class="p">)))):</span>
                    <span class="n">pdag</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">Y</span><span class="p">,</span> <span class="n">Z</span><span class="p">)</span>

            <span class="c1"># 3) for each X-Y with a directed path from X to Y, orient edges to X-&gt;Y</span>
            <span class="k">for</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">node_pairs</span><span class="p">:</span>
                <span class="k">for</span> <span class="n">path</span> <span class="ow">in</span> <span class="n">nx</span><span class="o">.</span><span class="n">all_simple_paths</span><span class="p">(</span><span class="n">pdag</span><span class="p">,</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">):</span>
                    <span class="n">is_directed</span> <span class="o">=</span> <span class="kc">True</span>
                    <span class="k">for</span> <span class="n">src</span><span class="p">,</span> <span class="n">dst</span> <span class="ow">in</span> <span class="n">path</span><span class="p">:</span>
                        <span class="k">if</span> <span class="n">pdag</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">dst</span><span class="p">,</span> <span class="n">src</span><span class="p">):</span>
                            <span class="n">is_directed</span> <span class="o">=</span> <span class="kc">False</span>
                    <span class="k">if</span> <span class="n">is_directed</span><span class="p">:</span>
                        <span class="n">pdag</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">Y</span><span class="p">,</span> <span class="n">X</span><span class="p">)</span>
                        <span class="k">break</span>

            <span class="c1"># 4) for each X-Z-Y with X-&gt;W, Y-&gt;W, and Z-W, orient edges to Z-&gt;W</span>
            <span class="k">for</span> <span class="n">X</span><span class="p">,</span> <span class="n">Y</span> <span class="ow">in</span> <span class="n">node_pairs</span><span class="p">:</span>
                <span class="k">for</span> <span class="n">Z</span> <span class="ow">in</span> <span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">&amp;</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">&amp;</span>
                          <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">Y</span><span class="p">))</span> <span class="o">&amp;</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">Y</span><span class="p">))):</span>
                    <span class="k">for</span> <span class="n">W</span> <span class="ow">in</span> <span class="p">((</span><span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">X</span><span class="p">))</span> <span class="o">-</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">X</span><span class="p">)))</span> <span class="o">&amp;</span>
                              <span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">Y</span><span class="p">))</span> <span class="o">-</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">Y</span><span class="p">)))</span> <span class="o">&amp;</span>
                              <span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">successors</span><span class="p">(</span><span class="n">Z</span><span class="p">))</span> <span class="o">&amp;</span> <span class="nb">set</span><span class="p">(</span><span class="n">pdag</span><span class="o">.</span><span class="n">predecessors</span><span class="p">(</span><span class="n">Z</span><span class="p">)))):</span>
                        <span class="n">pdag</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">W</span><span class="p">,</span> <span class="n">Z</span><span class="p">)</span>

            <span class="n">progress</span> <span class="o">=</span> <span class="n">num_edges</span> <span class="o">&gt;</span> <span class="n">pdag</span><span class="o">.</span><span class="n">number_of_edges</span><span class="p">()</span>

        <span class="k">return</span> <span class="n">pdag</span></div>

    <span class="nd">@staticmethod</span>
<div class="viewcode-block" id="ConstraintBasedEstimator.build_skeleton"><a class="viewcode-back" href="../../../estimators.html#pgmpy.estimators.ConstraintBasedEstimator.ConstraintBasedEstimator.build_skeleton">[docs]</a>    <span class="k">def</span> <span class="nf">build_skeleton</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span> <span class="n">independencies</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Estimates a graph skeleton (UndirectedGraph) from a set of independencies</span>
<span class="sd">        using (the first part of) the PC algorithm. The independencies can either be</span>
<span class="sd">        provided as an instance of the `Independencies`-class or by passing a</span>
<span class="sd">        decision function that decides any conditional independency assertion.</span>
<span class="sd">        Returns a tuple `(skeleton, separating_sets)`.</span>

<span class="sd">        If an Independencies-instance is passed, the contained IndependenceAssertions</span>
<span class="sd">        have to admit a faithful BN representation. This is the case if</span>
<span class="sd">        they are obtained as a set of d-seperations of some Bayesian network or</span>
<span class="sd">        if the independence assertions are closed under the semi-graphoid axioms.</span>
<span class="sd">        Otherwise the procedure may fail to identify the correct structure.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        nodes: list, array-like</span>
<span class="sd">            A list of node/variable names of the network skeleton.</span>

<span class="sd">        independencies: Independencies-instance or function.</span>
<span class="sd">            The source of independency information from which to build the skeleton.</span>
<span class="sd">            The provided Independencies should admit a faithful representation.</span>
<span class="sd">            Can either be provided as an Independencies()-instance or by passing a</span>
<span class="sd">            function `f(X, Y, Zs)` that returns `True` when X _|_ Y | Zs,</span>
<span class="sd">            otherwise `False`. (X, Y being individual nodes and Zs a list of nodes).</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        skeleton: UndirectedGraph</span>
<span class="sd">            An estimate for the undirected graph skeleton of the BN underlying the data.</span>

<span class="sd">        separating_sets: dict</span>
<span class="sd">            A dict containing for each pair of not directly connected nodes a</span>
<span class="sd">            separating set (&quot;witnessing set&quot;) of variables that makes then</span>
<span class="sd">            conditionally independent. (needed for edge orientation procedures)</span>

<span class="sd">        Reference</span>
<span class="sd">        ---------</span>
<span class="sd">        [1] Neapolitan, Learning Bayesian Networks, Section 10.1.2, Algorithm 10.2 (page 550)</span>
<span class="sd">            http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf</span>
<span class="sd">        [2] Koller &amp; Friedman, Probabilistic Graphical Models - Principles and Techniques, 2009</span>
<span class="sd">            Section 3.4.2.1 (page 85), Algorithm 3.3</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.estimators import ConstraintBasedEstimator</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.models import BayesianModel</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.independencies import Independencies</span>

<span class="sd">        &gt;&gt;&gt; # build skeleton from list of independencies:</span>
<span class="sd">        ... ind = Independencies([&#39;B&#39;, &#39;C&#39;], [&#39;A&#39;, [&#39;B&#39;, &#39;C&#39;], &#39;D&#39;])</span>
<span class="sd">        &gt;&gt;&gt; # we need to compute closure, otherwise this set of independencies doesn&#39;t</span>
<span class="sd">        ... # admit a faithful representation:</span>
<span class="sd">        ... ind = ind.closure()</span>
<span class="sd">        &gt;&gt;&gt; skel, sep_sets = ConstraintBasedEstimator.build_skeleton(&quot;ABCD&quot;, ind)</span>
<span class="sd">        &gt;&gt;&gt; print(skel.edges())</span>
<span class="sd">        [(&#39;A&#39;, &#39;D&#39;), (&#39;B&#39;, &#39;D&#39;), (&#39;C&#39;, &#39;D&#39;)]</span>

<span class="sd">        &gt;&gt;&gt; # build skeleton from d-seperations of BayesianModel:</span>
<span class="sd">        ... model = BayesianModel([(&#39;A&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;D&#39;), (&#39;C&#39;, &#39;E&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; skel, sep_sets = ConstraintBasedEstimator.build_skeleton(model.nodes(), model.get_independencies())</span>
<span class="sd">        &gt;&gt;&gt; print(skel.edges())</span>
<span class="sd">        [(&#39;A&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;C&#39;), (&#39;B&#39;, &#39;D&#39;), (&#39;C&#39;, &#39;E&#39;)]</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">nodes</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">nodes</span><span class="p">)</span>

        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">independencies</span><span class="p">,</span> <span class="n">Independencies</span><span class="p">):</span>
            <span class="k">def</span> <span class="nf">is_independent</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">,</span> <span class="n">Zs</span><span class="p">):</span>
                <span class="k">return</span> <span class="n">IndependenceAssertion</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="n">Y</span><span class="p">,</span> <span class="n">Zs</span><span class="p">)</span> <span class="ow">in</span> <span class="n">independencies</span>
        <span class="k">elif</span> <span class="n">callable</span><span class="p">(</span><span class="n">independencies</span><span class="p">):</span>
            <span class="n">is_independent</span> <span class="o">=</span> <span class="n">independencies</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">&quot;&#39;independencies&#39; must be either Independencies-instance &quot;</span> <span class="o">+</span>
                             <span class="s2">&quot;or a ternary function that decides independencies.&quot;</span><span class="p">)</span>

        <span class="n">graph</span> <span class="o">=</span> <span class="n">UndirectedGraph</span><span class="p">(</span><span class="n">combinations</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span>
        <span class="n">lim_neighbors</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="n">separating_sets</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">()</span>
        <span class="k">while</span> <span class="ow">not</span> <span class="nb">all</span><span class="p">([</span><span class="nb">len</span><span class="p">(</span><span class="n">graph</span><span class="o">.</span><span class="n">neighbors</span><span class="p">(</span><span class="n">node</span><span class="p">))</span> <span class="o">&lt;</span> <span class="n">lim_neighbors</span> <span class="k">for</span> <span class="n">node</span> <span class="ow">in</span> <span class="n">nodes</span><span class="p">]):</span>
            <span class="k">for</span> <span class="n">node</span> <span class="ow">in</span> <span class="n">nodes</span><span class="p">:</span>
                <span class="k">for</span> <span class="n">neighbor</span> <span class="ow">in</span> <span class="n">graph</span><span class="o">.</span><span class="n">neighbors</span><span class="p">(</span><span class="n">node</span><span class="p">):</span>
                    <span class="c1"># search if there is a set of neighbors (of size lim_neighbors)</span>
                    <span class="c1"># that makes X and Y independent:</span>
                    <span class="k">for</span> <span class="n">separating_set</span> <span class="ow">in</span> <span class="n">combinations</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">graph</span><span class="o">.</span><span class="n">neighbors</span><span class="p">(</span><span class="n">node</span><span class="p">))</span> <span class="o">-</span> <span class="nb">set</span><span class="p">([</span><span class="n">neighbor</span><span class="p">]),</span> <span class="n">lim_neighbors</span><span class="p">):</span>
                        <span class="k">if</span> <span class="n">is_independent</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">neighbor</span><span class="p">,</span> <span class="n">separating_set</span><span class="p">):</span>
                            <span class="n">separating_sets</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">((</span><span class="n">node</span><span class="p">,</span> <span class="n">neighbor</span><span class="p">))]</span> <span class="o">=</span> <span class="n">separating_set</span>
                            <span class="n">graph</span><span class="o">.</span><span class="n">remove_edge</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">neighbor</span><span class="p">)</span>
                            <span class="k">break</span>
            <span class="n">lim_neighbors</span> <span class="o">+=</span> <span class="mi">1</span>

        <span class="k">return</span> <span class="n">graph</span><span class="p">,</span> <span class="n">separating_sets</span></div></div>
</pre></div>

          </div>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">pgmpy 0.1.2 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >Module code</a> &#187;</li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2016, Ankur Ankan.
      Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.5.1.
    </div>
  </body>
</html>